A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem

摘要

A Bayesian optimization algorithm for the nurse scheduling problem ispresented, which involves choosing a suitable scheduling rule from a set foreach nurses assignment. Unlike our previous work that used Gas to implementimplicit learning, the learning in the proposed algorithm is explicit, ie.Eventually, we will be able to identify and mix building blocks directly. TheBayesian optimization algorithm is applied to implement such explicit learningby building a Bayesian network of the joint distribution of solutions. Theconditional probability of each variable in the network is computed accordingto an initial set of promising solutions. Subsequently, each new instance foreach variable is generated, ie in our case, a new rule string has beenobtained. Another set of rule strings will be generated in this way, some ofwhich will replace previous strings based on fitness selection. If stoppingconditions are not met, the conditional probabilities for all nodes in theBayesian network are updated again using the current set of promising rulestrings. Computational results from 52 real data instances demonstrate thesuccess of this approach. It is also suggested that the learning mechanism inthe proposed approach might be suitable for other scheduling problems.